//2009/08/21 00:03:43
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class KDoubleSubstrings
{
public:
    int howMuch(vector <string> str, int k)
    {
        int ret = 0;
        string s;
        for (int i=0; i<str.size(); i++) s += str[i];
        for (int i=0; i<s.size(); i++)
        {//Start from i with length j;
            for (int j=1; i+j+j<=s.size(); j++)
            {
                int count = 0;
                for (int p=i, q=i+j; p<i+j; p++, q++)
                    if (s[p] != s[q])
                        count++;
                if (count <=k)
                    ret++;
            }
        }
        return ret;
    }
};
